import java.util.Arrays;
import java.util.Date;
import java.util.Iterator;

/** SortingArray is used to contain references to the free Memory for the purpose of
 * sorting the Memory by starting address to facilitate the defragmentation of
 * adjacent blocks */
public class SortingArray implements Iterable<Memory>
{
	Memory[] memory;
	private int size;
	private Date date;

	/** SortingArray constructor initialized with length 4 */
	public SortingArray()
	{
		memory = new Memory[4];
		size = 0;
	}

	public String toString()
	{
		return Arrays.toString(memory);
	}

	/** Inserts a new Memory Block into the sorting array and resizes if needed
	 * @param m The memory to insert
	 */
	public void insert(Memory m)
	{
		if (size >= memory.length) // need to resize
			memory = copyArray(memory.length * 2);

		memory[size++] = m;
	}

	/** Removes a block of Memory from SortingArray by searching for its starting address 
	 * @param start
	 */
	public void remove(int start)
	{
		for (int i =0; i < memory.length; i++)
			if (memory[i] != null && memory[i].address() == start) {
				memory[i] = memory[size-1];
				memory[--size] = null;
				break;
			}
	}

	/** Creates a copy of the SortingArray with the specified length and returns a reference 
	 * @param length length of the new array
	 * @return reference to the new array */
	private Memory[] copyArray(int length)
	{
		Memory[] temp = new Memory[length];
		for (int i = 0, j = 0; i < memory.length; i++) {
			if (memory[i] != null)
				temp[j++] = memory[i];
		}
		return temp;
	}

	/** Performs a quicksort on a copy of the SortingArray and passes time data to the Statistics object
	 * @param s	Statistics object to pass data to
	 * @throws InterruptedException */
	public void quicksort(Statistics s) throws InterruptedException
	{
		date = new Date();
		Memory temp[] = copyArray(size);
		double duration = date.getTime();
		quickSort(temp, 0, temp.length-1);
		Thread.sleep(200);
		date = new Date();
		duration = date.getTime() - duration;
		if (size != 0)
			s.addQuick(duration/size);
	}	

	/** Recursive quicksort method that perfroms an in-place sort on the bounded section of the array
	 * chooses the first element as the pivot 
	 * @param array The array to sort
	 * @param low The lower bound
	 * @param high The upper bound
	 */
	private void quickSort(Memory[] array, int low, int high) 
	{
		if (low < high) {
			int mid = partition(array, low, high);

			quickSort(array, low, mid-1);
			quickSort(array, mid+1, high);
		}
		else return;
	}

	/** Partitions the array so that the values left of the pivot are smaller and the values to the right are larger
	 * The pivot is returned to it's proper sorted spot. Returns the index of the pivot 
	 * @param array The array to partition
	 * @param low The lower bound
	 * @param high The upper bound
	 * @return
	 */
	private int partition(Memory[] array, int low, int high) {
		int left = low, right = high+1;
		int pivot = array[left].address();

		while (true)
		{
			while (	array[++left].address() < pivot)
				if (left == high)
					break;
			while (	pivot < array[--right].address())
				if (right == low)
					break;
			if (left >= right)
				break;
			swap (array, left, right);
		}

		swap(array, low, right);
		return right;
	}

	/** Swaps 2 elements within the given array 
	 * @param array the array being swapped in
	 * @param first The first element
	 * @param second The second element */
	private void swap(Memory[] array, int first, int second) 
	{
		Memory temp = array[first];
		array[first] = array[second];
		array[second] = temp;		
	}

	/** Performs a bucketsort on the SortingArray and passes the time data to Statistics 
	 * @param s the Statstics object being passed to
	 * @throws InterruptedException */
	public void bucketsort(Statistics s) throws InterruptedException
	{	
		date = new Date();
		double duration = date.getTime();
		memory = bucketSort(memory);
		Thread.sleep(200);
		date = new Date();
		duration = date.getTime() - duration;
		if (size != 0)
			s.addBucket(duration/size);

	}	

	/** Finds the max address in the array, then creates an array of that length and places
	 * each Memory block in the SortingArray in the index of its address, effectively sorting the Memory.
	 * Returns the sorted Memory to the Sorting Array. 
	 * @param array The array to BucketSort
	 * @return reference to the sorted array
	 */
	private Memory[] bucketSort(Memory[] array) 
	{	
		int max = Integer.MIN_VALUE;
		Memory temp[];
		for (Memory m : array) 
		{
			if (m != null && m.address() > max)
				max = m.address();
		}
		if (max == Integer.MIN_VALUE)
			return array;
		temp = new Memory[max+1];

		for (Memory m: array){
			if (m != null)
				temp[m.address()] = m;
		}

		int i = 0;
		for (Memory m : temp) {
			if (m != null)
				array[i++] = m;
		}
		return array;		
	}

	/** Performs a partial defragmentation of the Memory in the SortingArray
	 * by combining adjacent blocks of Memory and returns a reference to the new SortingArray
	 * @return Reference to the new SortingArray
	 */
	public SortingArray defrag()
	{	
		SortingArray m = new SortingArray();
		if (memory[0] == null)
			return m;
		int blockSize = memory[0].size(), start = memory[0].address(), newSize = 0;

		for (int i = 1; i< size; i++) {			
			if (memory[i].address() == blockSize + start) 
				blockSize += memory[i].size();
			else {
				if (blockSize != 0) {
					m.insert(new Memory(blockSize, start, -1));
				}
				blockSize = memory[i].size();
				start = memory[i].address();
				newSize++;

			}
		}
		if (blockSize != 0) {
			m.insert(new Memory(blockSize, start, -1));
			size = ++newSize;
		}
		return m;
	}

	/** Iterator to iterate over the SortingArray 
	 */
	public Iterator<Memory> iterator() {
		return new SortingArrayIterator();
	}	

	/** SortingArrayIterator iterates over the SortingArray and returns values until it reaches a null
	 */
	private class SortingArrayIterator implements Iterator<Memory>
	{
		int start;

		/** Constructor for the  SortingArrayIterator sets tge starting index as 0
		 */
		public SortingArrayIterator()
		{
			start = 0;
		}

		/** Returns true if next element exists
		 * @return True if it has a next element */
		public boolean hasNext(){
			return start < size;
		}

		/** Returns the next element and advances the iterator
		 * if it has a next element
		 * @return Reference to the next element */
		public Memory next()
		{
			if (hasNext())
				return memory[start++];
			else return null;
		}

		public void remove() {
			//Not yet Implemented
		}
	}
}